package com.fantasy.sort;

import java.util.Date;

/**
 * 单路快速排序
 * */
public class QuickSortTest {

	public static void main(String[] args) {
		int[] arr = GenData.getIntRandomArray(100000, 10000);
		long start = new Date().getTime();
		new QuickSortTest().sort(arr);
		long end = new Date().getTime();
		System.out.println(end - start);
		//System.out.println(Arrays.toString(arr));
	}
	
	private void sort(int[] arr) {
		sort(arr, 0, arr.length - 1);
	}
	
	private void sort(int[] arr ,int l, int r) {
		if(l < r) {
			int postion = postion(arr , l, r);
			sort(arr, l, postion - 1);
			sort(arr, postion + 1, r);
			
		}
	}

	private int postion(int[] arr ,int l,int r) {
		int v = arr[l];
		int j = l;
		for (int i = l + 1; i <= r; i++) {
			if(arr[i] < v) {
				j ++;
				swap(arr, i, j);
			}
		}
		swap(arr, j, l);
		return j;
	}
	
	private void swap(int[] arr,int oldInx,int newInx) {
		int t = arr[oldInx];
		arr[oldInx] = arr[newInx];
		arr[newInx] = t;
	}
}
